package leetcode.array;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author Cheng Jun
 * Description: 给定两个数组，编写一个函数来计算它们的交集。
 * https://leetcode-cn.com/problems/intersection-of-two-arrays/
 * @version 1.0
 * @date 2021/12/29 13:18
 */
public class intersection {

    // 输入：nums1 = [1,2,2,1], nums2 = [2,2]
    // 输出：[2]
    // 思路：求交集且不能有重复元素
    // 根据去重，首先想到set 集合，先将nums1 加到set集合中，再遍历nums2 去匹配
    // 空间复杂度 O(m)，时间复杂度O(m+n)
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set = new HashSet<>();
        for (int num1 : nums1) {
            set.add(num1);
        }
        int tail = 0;
        for (int i = 0; i < nums2.length; i++) {
            if (set.contains(nums2[i])) {
                // 利用之前的 nums1 数组，节省空间
                nums1[tail++] = nums2[i];
                // 移除才能保证这个元素只被用了一次
                set.remove(nums2[i]);
            }
        }
        // 获取交集元素的数组
        return Arrays.copyOf(nums1, tail);
    }
}
